/*****************************************************
 * Prime number generation for 21 bits primes
 *
 *
 * Author: Majid Khonji - a part of Master thesis
 * created: 13/6/2009
 * 
 * Description
 * issues:
 * - 
 * -
 * -
 * 
 *
 ***************************************************/

#include <iostream>
#include <stdlib.h>
#include <math.h>
#include <vector>
using namespace std;

//typedef unsigned long fixedBitSizeInteger ;

inline bool IsPrime(unsigned long n)
// postcondition: returns true if n is prime, else returns false
// returns false if precondition is violated
{
    if (n < 2) // 1 and 0 aren't prime
        return false; // treat negative #'s as not prime
    else if (2 == n) // 2 is only even prime number
        return true;
    else if (n % 2 == 0) // even, can't be prime
        return false;
    else // number is odd
    {
        unsigned long  limit = ulong(sqrt(n) + 1); // largest divisor to check
        unsigned long divisor = 3; // initialize to smallest divisor
        // invariant: n has no divisors in range [2..divisor)
        while (divisor <= limit)
        { 
            if (n % divisor == 0) // n is divisible, not prime
            {
                return false;
            }
            divisor += 2; // check next odd number
        }
        return true; // number must be prime
    }
}

inline unsigned long next_prime(unsigned long n) {
    unsigned long increment;
    if (n<7)
    {
        if (n==1 || n==0 || n==2) return 2;
        if (n==3) return 3;
        if (n==5) return 5;
    }
    while(n%6!=1 && n%6!=5) n+=1;
    increment = (n%6==1) ? 4 : 2;
    while(!IsPrime(n))
    {
        n+=increment;
        increment = 6 - increment;
    }
    return n;
}


inline vector< fixedBitSizeInteger > generate21bitsprimes()
{
    unsigned long p ;
    vector< fixedBitSizeInteger >tabprime;

    for ( p = next_prime(ulong(1048576)); p < (unsigned long)(2097152);  p=next_prime(p+2) ) 
    {  
        tabprime.push_back( p ) ; 
    }
    return tabprime;
}

inline void  generate21bitsprimes(vector<fixedBitSizeInteger>* tabprime, size_t first, size_t last)
{
    fixedBitSizeInteger p ;
    int i;
    for (i=0, p = next_prime(fixedBitSizeInteger(1048576)); p < fixedBitSizeInteger(2097152) && (i < last) ;  p=next_prime(p+2), i++ ) 
    {  
        if(i >= first)
           tabprime->push_back( p) ; 
    }
}


